package com.tgy.leetcode;

/**
 * @Author: tgy
 * @Date: 12/18/20 11:39 AM
 */
public class _333_最大BST子树 {

    private static class BSTInfo{

        /**
         * 根节点
         */
        TreeNode root;
        /**
         * bst的元素个数
         */
        int size;
        /**
         * bst树中的最大值
         */
        int max;
        /**
         * bst树中的最小值
         */
        int min;

        public BSTInfo(TreeNode root, int size, int max, int min) {
            this.root = root;
            this.size = size;
            this.max = max;
            this.min = min;
        }
    }

    public int largeBSTSubtree(TreeNode root){

        if (root == null) {

            return 0;
        }

        return getMaxBST(root).size;
    }

    public BSTInfo getMaxBST(TreeNode root) {

        if (root == null) {

            return null;
        }

        BSTInfo leftBSTInfo = getMaxBST(root.left);
        BSTInfo rightBSTInfo = getMaxBST(root.right);

        /**
         * 如果 root.val > leftBSTInfo.max &&
         */

        if (leftBSTInfo != null && leftBSTInfo.root == root.left && root.val > leftBSTInfo.max
                && rightBSTInfo != null && rightBSTInfo.root == root.right && root.val < rightBSTInfo.min) {

            return new BSTInfo(root,leftBSTInfo.size + rightBSTInfo.size + 1,leftBSTInfo.min,rightBSTInfo.max);
        }

        if (leftBSTInfo == null && rightBSTInfo == null) {

            return new BSTInfo(root,1,root.val,root.val);
        }

        if (leftBSTInfo == null && rightBSTInfo != null) {

            if (rightBSTInfo.root == root) {

                rightBSTInfo.root = root;
                rightBSTInfo.size++;
                rightBSTInfo.min = root.val;
            }

            return rightBSTInfo;
        }

        if (leftBSTInfo != null && rightBSTInfo == null){

            if (leftBSTInfo.root == root) {

                leftBSTInfo.root = root;
                leftBSTInfo.size++;
                leftBSTInfo.max = root.val;
            }

            return  leftBSTInfo;
        }

        return leftBSTInfo.size > rightBSTInfo.size ? leftBSTInfo:rightBSTInfo;
    }

}
